package com.itheima.leetcode.od.b.graph.topo;

import com.itheima.datastructure.graph.Edge;
import com.itheima.datastructure.graph.Vertex;

import java.util.*;
import java.util.stream.Collectors;

/**
 * (B卷,200分)- 服务失效判断（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 某系统中有众多服务，每个服务用字符串（只包含字母和数字，长度<=10）唯一标识，服务间可能有依赖关系，如A依赖B，则当B故障时导致A也故障。
 * <p>
 * 依赖具有传递性，如A依赖B，B依赖C，当C故障时导致B故障，也导致A故障。
 * <p>
 * 给出所有依赖关系，以及当前已知故障服务，要求输出所有正常服务。
 * <p>
 * 依赖关系：服务1-服务2 表示“服务1”依赖“服务2”
 * <p>
 * 不必考虑输入异常，用例保证：依赖关系列表、故障列表非空，且依赖关系数，故障服务数都不会超过3000，服务标识格式正常。
 * <p>
 * 输入描述
 * <p>
 * 半角逗号分隔的依赖关系列表（换行）
 * <p>
 * 半角逗号分隔的故障服务列表
 * <p>
 * 输出描述
 * <p>
 * 依赖关系列表中提及的所有服务中可以正常工作的服务列表，用半角逗号分隔，按依赖关系列表中出现的次序排序。
 * <p>
 * 特别的，没有正常节点输出单独一个半角逗号。
 * <p>
 * 用例
 * <p>
 * 输入	a1-a2,a5-a6,a2-a3
 * <p>
 * a5,a2
 * <p>
 * 输出	a6,a3
 * 说明
 * a1依赖a2，a2依赖a3，所以a2故障，导致a1不可用，但不影响a3；a5故障不影响a6。
 * <p>
 * 所以可用的是a3、a6，在依赖关系列表中a6先出现，所以输出:a6,a3。
 * <p>
 * 输入	a1-a2
 * <p>
 * a2
 * <p>
 * 输出	,
 * 说明	a1依赖a2，a2故障导致a1也故障，没有正常节点，输出一个逗号。
 * <p>
 * 题目解析
 * <p>
 * 我的解题思路是：
 * <p>
 * 根据第一行输入的依赖关系，统计出每个服务的直接子服务，记录在next中。
 * <p>
 * 另外由于题目输出描述中说：输出的服务要按照：
 * <p>
 * 按依赖关系列表中出现的次序排序。
 * <p>
 * 因此，这里我还定义了一个first，用于记录每个服务第一次出现的位置。
 * <p>
 * 当上面统计好后，就可以遍历第二行输入的故障服务列表了。
 * <p>
 * 每遍历到一个故障服务，则删除next中对应服务，但是删除前，需要先记录将要删除服务的所有子服务。删除当前故障服务后，继续递归删除其子服务。
 * <p>
 * 这样next剩下的就是正常服务了。
 * <p>
 * 此时再按照first记录的出现位置对剩余的正常服务排序即可，
 */
public class ServiceFailureJudgment {
    public static void main(String[] args) {
        /*Scanner scanner = new Scanner(System.in);

        // 读取依赖关系列表，存储为列表
        String[] dependencyInput = scanner.nextLine().split(",");
        List<String[]> dependencies = new ArrayList<>();
        for (String dep : dependencyInput) {
            dependencies.add(dep.split("-"));
        }

        // 读取故障服务列表
        List<String> failedServices = Arrays.asList(scanner.nextLine().split(","));*/

        String input1 = "a1-a2,a5-a6,a2-a3";
        String input2 = "a5,a2";

        List<String[]> dependencies = Arrays.stream(input1.split(","))
                .map(s -> s.split("-"))
                .collect(Collectors.toList());

        List<String> failedServices = Arrays.stream(input2.split(","))
                .collect(Collectors.toList());

        System.out.println(getResult(dependencies, failedServices));
        System.out.println(getResult2(dependencies, failedServices));
    }

    public static String getResult(List<String[]> dependencies, List<String> failedServices) {
        // 存储服务依赖关系的映射（被依赖的服务 -> 依赖它的服务）
        Map<String, Set<String>> dependencyMap = new HashMap<>();

        // 记录服务首次出现的顺序，确保最终输出按输入顺序排序
        Map<String, Integer> serviceOrder = new HashMap<>();
        int order = 0;

        // 构建服务依赖映射
        for (String[] dependency : dependencies) {
            String dependent = dependency[0], prerequisite = dependency[1];

            // 初始化依赖关系映射
            dependencyMap.putIfAbsent(dependent, new HashSet<>());
            dependencyMap.putIfAbsent(prerequisite, new HashSet<>());
            dependencyMap.get(prerequisite).add(dependent);

            // 记录服务首次出现顺序
            serviceOrder.putIfAbsent(dependent, order++);
            serviceOrder.putIfAbsent(prerequisite, order++);
        }

        // 递归删除所有受影响的服务
        for (String failedService : failedServices) {
            removeAffectedServices(dependencyMap, failedService);
        }

        // 获取所有仍然正常运行的服务
        List<String> activeServices = new ArrayList<>(dependencyMap.keySet());

        // 如果所有服务都故障，输出一个逗号，否则按顺序输出正常服务
        if (activeServices.isEmpty()) {
            return ",";
        } else {
            activeServices.sort(Comparator.comparingInt(serviceOrder::get));
            return activeServices.stream()
                    .sorted((a, b) -> serviceOrder.get(a) - serviceOrder.get(b))
                    .collect(Collectors.joining(","));
        }
    }

    /**
     * 递归删除受影响的服务
     *
     * @param dependencyMap 存储服务依赖关系的映射
     * @param failedService 当前故障的服务
     */
    private static void removeAffectedServices(Map<String, Set<String>> dependencyMap, String failedService) {
        if (dependencyMap.containsKey(failedService)) {
            Set<String> affected = dependencyMap.get(failedService);
            dependencyMap.remove(failedService);
            // 继续递归删除受影响的服务
            for (String service : affected) {
                removeAffectedServices(dependencyMap, service);
            }
        }
    }

    /**
     * 拓扑的广度遍历，有点炫技了，我写滴比作者可读性更差
     *
     * @param dependencies
     * @param failedServices
     * @return
     */
    public static String getResult2(List<String[]> dependencies, List<String> failedServices) {

        /**
         * 将所有的参数初始化进 图（用map装）
         */
        HashMap<String, Vertex> graph = new HashMap<>();
        dependencies.stream().forEach(strings -> {
            graph.putIfAbsent(strings[0], new Vertex(strings[0]));
            graph.putIfAbsent(strings[1], new Vertex(strings[1]));
            graph.get(strings[1]).edges.add(new Edge(graph.get(strings[0])));
        });

        Collection<Vertex> vertices = graph.values();
        for (Vertex vertex : vertices) {
            for (Edge edge : vertex.edges) {
                edge.linked.inDegree++;
            }
        }

        LinkedList<Vertex> curQueue = new LinkedList<>();
        List<String> result = new ArrayList<>();
        for (Vertex vertex : vertices) {
            if (0 == vertex.inDegree && !failedServices.contains(vertex.name)) {
                curQueue.offer(vertex);
            }
        }

        // 敲重点，这里需要通过定义一个临时的 nextQueue 来进行广度按层排序
        while (!curQueue.isEmpty()) {
            curQueue.sort((a, b) -> b.name.compareTo(a.name)); // 降序排序（大顶堆）

            LinkedList<Vertex> nextQueue = new LinkedList<>();
            while (!curQueue.isEmpty()) {
                Vertex vertex = curQueue.poll();
                result.add(vertex.name);
                for (Edge edge : vertex.edges) {
                    if (!failedServices.contains(edge.linked.name)
                            && 0 == --edge.linked.inDegree) {
                        nextQueue.offer(edge.linked);
                    }
                }
            }
            curQueue = nextQueue;
        }

        if (0 == result.size()) {
            return ",";
        } else {
            return result.stream().collect(Collectors.joining(","));
        }
    }
}